import java.util.Arrays;

public class MergeSort2 {
    private MergeSort2() {
    }

    public static <E extends Comparable<E>> void sortBU(E[] arr) {
        sortBU(arr, 0, arr.length - 1);
    }

    //自底向上的归并排序
    public static <E extends Comparable<E>> void sortBU(E[] arr, int l, int r) {
        //将原数组从l到r+1的区间复制一份出来
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int n = arr.length;
        //遍历合并的区间长度
        //每次区间翻一倍 1,2,4,8,16...
        for (int sz = 1; sz < n; sz += sz) {
            //遍历合并的两个区间的起始位置  [i,i+sz-1]和[i+sz+sz-1,n-1]
            for (int i = 0; i + sz < n; i += sz + sz) {
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    mergeBU(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), temp);
            }
        }
    }

    //合并两个有序的区间
    private static <E extends Comparable<E>> void mergeBU(E[] arr, int l, int mid, int r, E[] temp) {

        // mid代表右分区的开始
        int i = l, j = mid + 1;

        //每轮循环为arr[k]赋值
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = temp[k - l];
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                //arr[i]和arr[j]
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
